﻿//https://leetcode.cn/problems/greatest-sum-divisible-by-three/

class Solution {
public:
    int maxSumDivThree(vector<int>& nums)
    {
        int sum = 0;
        int x1 = 0x3f3f3f3f, x2 = 0x3f3f3f3f, y1 = 0x3f3f3f3f, y2 = 0x3f3f3f3f;
        for (auto x : nums)
        {
            sum += x;
            if (x % 3 == 1)
            {
                if (x < x1)
                {
                    x2 = x1;
                    x1 = x;
                }
                else if (x < x2)
                    x2 = x;
            }
            else if (x % 3 == 2)
            {
                if (x < y1)
                {
                    y2 = y1;
                    y1 = x;
                }
                else if (x < y2)
                    y2 = x;
            }
        }

        if (sum % 3 == 0) return sum;
        else if (sum % 3 == 1) return max(sum - x1, sum - y1 - y2);
        return max(sum - x1 - x2, sum - y1);

    }
};